#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define NR_CPU 2

struct List {
	int start;
	int end;
	int *data;
};

void *sort(void *list)
{
	struct List *cpu;
	struct result *result;
	int i,j;

	cpu = (struct List *)list;
	for(i = cpu->start; i < cpu->end - 1; i++) {
		int min = i;
		for(j = i + 1; j < cpu->end; j++) {
			if(cpu->data[j] < cpu->data[min]) 
				min = j;
		}
		int temp = cpu->data[i];
		cpu->data[i] = cpu->data[min];
		cpu->data[min] = temp;
	}
	
	/*for(i = cpu->start; i < cpu->end; i++)
		printf("%d ",cpu->data[i]);
	printf("\n");*/
	return NULL;
}

int main()
{
	int i,j;
	int length;
	printf("put list length: ");
	scanf("%d",&length);
	
	int *datas = (int *)malloc(length * sizeof(int));
	printf("put %d datas: ",length);
	for(i = 0; i < length; i++)
		scanf("%d",datas + i);
	
	pthread_t workers[NR_CPU];
	struct List Lists[NR_CPU];

	for(i = 0; i < NR_CPU; i++) {
		struct List *cpu;
		cpu = &Lists[i];
		cpu->start = length / 2 * i;
		cpu->end = length / 2 * (i + 1);
		if(length % 2 == 1 && i % 2 == 1) 
			cpu->end += 1;
		cpu->data = datas;
		pthread_create(&workers[i], NULL, sort, cpu);
	}

	for(i = 0; i < NR_CPU; i++)
		pthread_join(workers[i], NULL);

	int *result = (int *)malloc(length * sizeof(int));
	i = Lists[0].start;
	j = Lists[1].start;
	int k = 0;
	while(i < Lists[0].end && j < Lists[1].end) {
		if(Lists[0].data[i] <= Lists[1].data[j])
			result[k++] = Lists[0].data[i++];
		else result[k++] = Lists[1].data[j++];
	}
	while(i < Lists[0].end) result[k++] = Lists[0].data[i++];
	while(j < Lists[1].end) result[k++] = Lists[1].data[j++];
	
	printf("result: ");
	for(i = 0; i < length; i++)
		printf("%d ",result[i]);
	printf("\n");

	return 0;
}
